This paper introduces and studies online conversion with switching costs (OCS), a novel class of online problems motivated by emerging control problems in the design of sustainable systems. We consider both minimization (OCS-min) and maximization (OCS-max) variants of the problem. In OCS-min, an online player aims to purchase one item over a sequence of time-varying cost functions and decides the fractional amount of item to purchase in each round. The player must purchase the entire item before a deadline, and they incur a movement cost whenever their decision changes, i.e., whenever they purchase different amounts of the item in consecutive time steps. From the player's perspective, the goal is to minimize their total cost, including the total purchasing cost and any movement cost incurred over the time horizon. In OCS-max, the setting is almost the same, except the player sells an item fractionally according to time-varying price functions, so the goal is to maximize their total profit, and any movement costs are subtracted from the revenue. In both settings, the cost/price functions are revealed one by one in an online manner, and the player makes an irrevocable decision at each time step without the knowledge of future cost/price functions. Our motivation behind introducing OCS is an emerging class of carbon-aware problems such as carbon-aware electric vehicle (EV) charging [12] and carbon-aware compute shifting [1, 3, 22, 23, 46, 57], which have attracted significant attention in recent years.

Computer science pioneer Edsger Dijkstra's algorithms form the backbone of many computer subroutines, thanks to their elegant efficiency. However, seemingly subtle changes in requirements can lead to these often conceptually simple formulations failing to provide an accurate answer. The replacement algorithms provide the correct answers but are frequently orders of magnitude slower. A recent breakthrough in combinatorial techniques has shown how these early algorithms can be revived. Shortest-path problems provide good examples of the sensitivity of an algorithm to the specifics of their requirements.

We study the complexity of Destructive Shift Bribery. In this problem, we are given an election with a set of candidates and a set of voters (each ranking the candidates from the best to the worst), a despised candidate $d$, a budget $B$, and prices for shifting $d$ back in the voters' rankings. The goal is to ensure that $d$ is not a winner of the election. We show that this problem is polynomial-time solvable for scoring protocols (encoded in unary), the Bucklin and Simplified Bucklin rules, and the Maximin rule, but is NP-hard for the Copeland rule. This stands in contrast to the results for the constructive setting (known from the literature), for which the problem is polynomial-time solvable for $k$-Approval family of rules, but is NP-hard for the Borda, Copeland, and Maximin rules. We complement the analysis of the Copeland rule showing W-hardness for the parameterization by the budget value, and by the number of affected voters. We prove that the problem is W-hard when parameterized by the number of voters even for unit prices. From the positive perspective we provide an efficient algorithm for solving the problem parameterized by the combined parameter the number of candidates and the maximum bribery price (alternatively the number of different bribery prices).

Given an election, a preferred candidate p, and a budget, the SHIFT BRIBERY problem asks whether p can win the election after shifting p higher in some voters' preference orders. Of course, shifting comes at a price (depending on the voter and on the extent of the shift) and one must not exceed the given budget. We study the (parameterized) computational complexity of S HIFT BRIBERY for multiwinner voting rules where winning the election means to be part of some winning committee. We focus on the well-established SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule, since the original rule is NP-hard to compute. We show that SHIFT BRIBERY tends to be harder in the multiwinner setting than in the single-winner one by showing settings where SHIFT BRIBERY is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. Moreover, we show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin-Courant rule sometimes affects the complexity of SHIFT BRIBERY.

We study the (parameterized) complexity of Shift Bribery for multiwinner voting rules. We focus on the SNTV, Bloc, k-Borda, and Chamberlin-Courant rules, as well as on approximate variants of the Chamberlin-Courant rule, since the original rule is NP-hard to compute. We show that Shift Bribery tends to be significantly harder in the multiwinner setting than in the single-winner one by showing settings where Shift Bribery is easy in the single-winner cases, but is hard (and hard to approximate) in the multiwinner ones. We show that the non-monotonicity of those rules which are based on approximation algorithms for the Chamberlin--Courant rule sometimes affects the complexity of Shift Bribery.

Matching markets are often used in exchange settings (e.g., supply chain) to increase economic efficiency while respecting certain global constraints on outcomes. We investigate their application to pricing and cost sharing in group purchasing of electricity in smart grid settings. The task is complicated by the complexities of producer cost functions due to constraints on generation from different sources (they are sufficiently complex that welfare-optimal matchings are not usually in equilibrium). We develop two novel cost sharing schemes: one based on Shapley values that is "fair," but computationally intensive; and one that captures many of the essential properties of Shapley pricing, but scales to large numbers of consumers. Empirical results show these schemes achieve a high degree of stability in practice and can be made more stable by sacrificing small amounts (< 2%) of social welfare.

In the Shift Bribery problem, we are given an election (based on preference orders), a preferred candidate p, and a budget. The goal is to ensure that p wins by shifting p higher in some voters' preference orders. However, each such shift request comes at a price (depending on the voter and on the extent of the shift) and we must not exceed the given budget. We study the parameterized computational complexity of Shift Bribery with respect to a number of parameters (pertaining to the nature of the solution sought and the size of the election) and several classes of price functions. When we parameterize Shift Bribery by the number of affected voters, then for each of our voting rules (Borda, Maximin, Copeland) the problem is W[2]-hard. If, instead, we parameterize by the number of positions by which p is shifted in total, then the problem is fixed-parameter tractable for Borda and Maximin, and is W[1]-hard for Copeland. If we parameterize by the budget for the cost of shifting, then the results depend on the price function class. We also show that Shift Bribery tends to be tractable when parameterized by the number of voters, but that the results for the number of candidates are more enigmatic.

In this paper, we propose a novel decentralised control mechanism to manage micro-storage in the smart grid. Our approach uses an adaptive pricing scheme that energy suppliers apply to home smart agents controlling micro-storage devices. In particular, we prove that the interaction between a supplier using our pricing scheme and the actions of selfish micro-storage agents forms a globally stable feedback loop that converges to an efficient equilibrium. We further propose a market strategy that allows the supplier to reduce wholesale purchasing costs without increasing the uncertainty and variance for its aggregate consumer demand. Moreover, we empirically evaluate our mechanism (based on the UK grid data) and show that it yields savings of up to 16% in energy cost for consumers using storage devices with average capacity 10 kWh. Furthermore, we show that it is robust against extreme system changes.

We explore the striking mathematical connections that exist between market scoring rules, cost function based prediction markets, and no-regret learning. We show that any cost function based prediction market can be interpreted as an algorithm for the commonly studied problem of learning from expert advice by equating trades made in the market with losses observed by the learning algorithm. If the loss of the market organizer is bounded, this bound can be used to derive an O(sqrt(T)) regret bound for the corresponding learning algorithm. We then show that the class of markets with convex cost functions exactly corresponds to the class of Follow the Regularized Leader learning algorithms, with the choice of a cost function in the market corresponding to the choice of a regularizer in the learning problem. Finally, we show an equivalence between market scoring rules and prediction markets with convex cost functions. This implies that market scoring rules can also be interpreted naturally as Follow the Regularized Leader algorithms, and may be of independent interest. These connections provide new insight into how it is that commonly studied markets, such as the Logarithmic Market Scoring Rule, can aggregate opinions into accurate estimates of the likelihood of future events.